package com.jxb.test20241216;

import java.util.ArrayList;
import java.util.List;

public class Sort6 {

    public static void main(String[] args) {

    }

    public static int[] sortArray(int[] nums) {
        if (nums == null) {
            return null;
        }

        //构建桶
        int max = 0,min = 0;
        for (int i = 0; i<nums.length;i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
            if (nums[i] < min) {
                min = nums[i];
            }
        }

        //获取桶的数量
        int bucketCount = (max - min) / 2 + 1;

        //构建桶
        List<Integer[]> buckets = new ArrayList<>(bucketCount);
        for (int i = 0;i<bucketCount;i++) {
            buckets.add(new Integer[2]);
        }

        //遍历原数组，添加桶数据
        for (int i =0;i<nums.length;i++) {
            int i1 = (nums[i] - min)/2;//????
            Integer[] subBucket = buckets.get(i1);
            if (subBucket[0] != null) {
                subBucket[1] = nums[i];
            }else {
                subBucket[0] = nums[i];
            }
        }
        //对桶中的元素进行排序，将排好序的数据放入原数组中
        int j = 0;
        for (Integer[] bucket : buckets) {
            xSort(bucket);
            for (int k = 0;k<bucket.length;k++) {
                if (bucket[k] != null) {
                    nums[j] = bucket[k];
                    j++;
                }
            }
        }
        return nums;
    }

    private static void xSort(Integer[] bucket) {
        //当前待排序的内容
        int currentValue;
        for (int i = 0;i<bucket.length-1;i++){
            //已被排序的数据索引
            int preIndex = i;
            //获取当前需要排序的数据
            if (bucket[preIndex + 1]!=null) {
                currentValue = bucket[preIndex + 1];
                while (preIndex >= 0 && currentValue<bucket[preIndex]) {
                    //将已排序的数据向后移动一位
                    bucket[preIndex + 1] = bucket[preIndex];
                    preIndex--;
                }
                //将当前需要排序的数据向前移动一位
                bucket[preIndex + 1] = currentValue;
            }
        }
    }

}
